In a communication system, a transmitter transmits the communication signal to a remote receiver, in a way that fading and errors of the communication signal are often caused in a wireless transmission channel. Hence, the communication signal first need be convolutionally encoded before being transmitted to the remote receiving end. The receiving end receives the convolutionally encoded communication signal and then performs convolutional decoding to obtain the communication signal, so as to reduce signal errors through the convolutional encoding/decoding process. The convolutional encoding is a channel encoding by a channel encoder. The output of codeword in the channel encoding is not only related to the present inputted information bit, but also affected by the previous inputted information bits, i.e., the codeword has memory. In general, the convolutional code has three parameters (n, k, m). That is, each k information bits generate n-bit codeword, and the output of the n-bit codeword is determined by the previous m information bits and the present inputted k information bits, wherein the ratio R=k/n is called the code rate that represents the information of each codeword, and m is defined as a memory order that represents the storage time unit of the inputted information bits in the encoder, i.e. the register number the encoder needs. The higher memory order is, the higher the correcting ability for the convolutional coding gets. Another frequently used coefficient is a constraint length. For a k=1 encoder, the constraint length can be represented as K=m+1 to represent the maximum bit number affected by the output bits of the encoder.
The convolutional encoder can be viewed as a finite state machine. The convolutional encoder uses a state diagram to describe its input/output relation, and all states are defined by the content in the shift register in the encoder.
FIG. 1A is a state diagram of a conventional (2, 1, 2) convolutional code. FIG. 1B is a trellis diagram of a conventional (2, 1, 2) convolutional code. A (2, 1, 2) convolutional encoder has the memory order m=2, and hence it has 22=4 states. For example, its state diagram is as FIG. 1A, and the corresponding state transition per unit time can be further represented by a trellis diagram as FIG. 1B by expanding the state diagram.
From a trellis diagram, the path and the corresponding codeword for each inputted information sequence are observed. For example, state S0 is changed to state S0 or state S1 by inputting an information bit 0 or 1. The outputted codeword is related to not only the present state, but also the inputted information bit. At the receiving end, the codeword transmitted can be identified through the receiving sequence and the trellis diagram—such identification process is called decoding.
Numerous conventional decoding algorithms for the convolutional encoding are proposed, and among the available decoding algorithms, Viterbi algorithm is a likelihood decoding algorithm that achieves more satisfactory efficiency. In the following description, a (2, 1, 2) convolutional code is taken for example to illustrate how the convolutional code is decoded by the Viterbi algorithm. First some terms are defined. The distance between two codewords represents the number of unequal bits of two codewords. For example, the distance between (1 0) and (0 1) is 2, and the distance between (1 1) and (0 1) is 1. The branch metric represents the distance between the receiving sequence and the branch codeword. At time T=t, the branch metric from state Si to Sj is denoted as BMi,j,t. The accumulated path metric represents the minimum value of the sum of all the branch metrics to state Sj till T=t, and is denoted as S1. The survivor path represents the path entering the state with the minimum accumulated branch metric after decoding.
Suppose the initial state is at S0, time starts from T=0, and the transmitting information sequence is u=(0,1,0,1,0). After the (2, 1, 2) convolutional encoder, the codeword v=(00, 11, 10, 00, 10, 11, 00) is obtained. Influenced by the binary symmetric channel, the receiving codeword sequence is r=(00, 11, 10, 00, 10, 11, 10), wherein one bit represented in boldface is incorrect.
FIG. 2 is a trellis diagram of the conventional Viterbi algorithm. In FIG. 2, states S0, S1, S2 and S3 are arranged from the bottom to the top, the dotted line is the path with an input of 0, the straight line is the path with an input of 1, and the codeword on the path is the branch codeword. When decoding, from state S0 to state S0 and S1, one calculates the branch metrics, BM0,0,0=0 and BM0,1,0=2. The bolder path is the survivor path of each state at the time T=5. The value beside the state is the accumulated path metric of the state at that time. The boldest path is the preferred survivor path (PM2,5=0) when the decoding process is finished at the time T=5. By back-tracing the survivor path, the original information sequence u=(0, 1, 0, 1, 0, 0, 0) can be obtained. The last two zeros are used to recover the content of the register to state S0 after decoding so that the next decoding process can be started from the state S0.
However, the prior art does not mention a solution for a situation where the accumulated path metric is similar or equal. If one of the survivor paths is determined directly instead of specifically attending such situation, opportunities of the other paths are denied to likely result in decoding errors. Therefore, it is urgently needed a decoding method and associated apparatus for solving issues of equal or similar accumulated path metrics.